package com.sx.sx1.lintcode.day717;

public class LC119 {
    static class Solution {
        /**
         * @param word1: A string
         * @param word2: A string
         * @return: The minimum number of steps
         */
        public int minDistance(String word1, String word2) {
            //动态规划：样本对应模型
            int n= word1.length();
            int m = word2.length();
            int[][] dp = new int[n+1][m+1];
            for (int i = 0; i <=n ; i++) {
                for (int j = 0; j <=m ; j++) {
                    dp[i][j] =-1;
                }
            }


            return dfs(word1,word2,n,m,1,dp);
        }

        public int dfs(String s1,String s2,int i,int j,int cnt,int[][] dp){
            if(dp[i][j] !=-1){
                return dp[i][j];
            }

            int ans =s1.length();

            if(i==0 && j==0) ans=0;
            else if(i==0) ans = cnt*j;
            else if(j ==0) ans = cnt*i;
            else{
                ans = dfs(s1,s2,i-1,j-1,cnt,dp)+(s1.charAt(i-1) == s2.charAt(j-1) ? 0:cnt);
                ans= Math.min(ans,dfs(s1,s2,i-1,j,cnt,dp)+cnt);
                ans= Math.min(ans,dfs(s1,s2,i,j-1,cnt,dp)+cnt);
            }
            dp[i][j] =ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.minDistance("horse","ros"));
        System.out.println(obj.minDistance("intention","execution"));
    }

}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有197条未读消息，请及时查看
119 · 编辑距离
算法
中等
通过率
40%

题目
题解36
笔记
讨论99+
排名
记录
描述
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你可进行三种操作：

插入一个字符
删除一个字符
替换一个字符
最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


l
e
n
(
w
o
r
d
1
)
,
l
e
n
(
w
o
r
d
2
)
<
=
500
len(word1),len(word2)<=500

样例
样例 1：

输入：

word1 = "horse"
word2 = "ros"
输出：

3
解释：

horse -> rorse (替换 'h' 为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

样例 2：

输入：

word1 = "intention"
word2 = "execution"
输出：

5
解释：

intention -> inention (删除 't')
inention -> enention (替换 'i' 为 'e')
enention -> exention (替换 'n' 为 'x')
exention -> exection (替换 'n' 为 'c')
exection -> execution (插入 'u')

相关知识
学习《算法求职课——百题精讲》课程中的15.3编辑距离-视频讲解相关内容 ，了解更多相关知识！
标签
相关题目

77
最长公共子序列
中等

623
K步编辑
困难

640
一次编辑距离
中等
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
